package structure;

import java.util.ArrayList;
import node.AVLNode;
import node.BinaryNode;
import node.Insertable;

/**
 *
 * @author Vojta
 */
public class BinaryTree implements DataStructure {
    
    protected BinaryNode root;

    /**
     * Prida uzel do stromu.
     * @param i Pridavany uzel.
     * @return True, pokud operace skonci uspesne, false v pripade neuspechu.
     */
    public boolean add(Insertable i) {
        if (root == null) {
            root = (BinaryNode) i;
            return true;
        }
        return root.addChild((BinaryNode) i);
    }
    
    /**
     * Odebere uzel ze stromu podle klice.
     * @param id Klic.
     * @return Odebirany uzel, null v pripade, ze klic neodpovida zadnemu uzlu.
     */
    public Insertable delete(int id) {
        BinaryNode toDelete = (BinaryNode) find(id);
        if (toDelete == null) {
            return null;
        }
        if (toDelete.remove()) {
            root = null;
        } else {
            root = findRoot();
        }
        return toDelete;
    }

    /**
     * Najde uzel podle klice.
     * @param id Klic.
     * @return Hledany uzel, null v pripade neuspechu.
     */
    public Insertable find(int id) {
        return root.find(id);
    }
    
    /**
     * Pocet uzlu ve stromu.
     * @return 
     */
    public int size() {
        return (root != null) ? root.countDescedant() : 0;
    }
    
    /**
     * Hloubka stromu.
     * @return 
     */
    public int height() {
        return (root != null) ? root.subtreeHeight() : 0;
    }
    
    public boolean isEmpty() {
        return (root == null) ? true : false;
    }
    
    /**
     * Maximalni prvek ve stromu.
     * @return 
     */
    public BinaryNode max() {
        return findMax(root);
    }
    
    /**
     * Minimalni prvek ve stromu.
     * @return 
     */
    public BinaryNode min() {
        return findMin(root);
    }
    
    public ArrayList<Identifiable> sort() {
        ArrayList<Identifiable> l = new ArrayList<Identifiable>();
        root.sort(l);
        return l;
    }
    
    private BinaryNode findMax(BinaryNode root) {
        return root.findMax();
    }
    
    private BinaryNode findMin(BinaryNode root) {
        return root.findMin();
    }

    public BinaryNode getRoot() {
        return root;
    }
    
    @Override
    public String toString(){
        return root.toString(0);
    }

    protected BinaryNode findRoot() {
        BinaryNode n = root;
        while (n.getParent() != null) {
            n = n.getParent();
        }
        return n;
    }
    
}
